The present invention relates to the creation, coding, processing and detection of sequences comprised of binary and multi-value digital (non-binary) symbols. One aspect of the present invention relates to improved detection of sequences as well as the improved distinguishing between sequences.
Another aspect of the invention relates to the creation of signals wherein individual sequences represent one of n symbols with n an integer greater than 2.
The present invention has application in telecommunication systems, control systems and other applications. A specific example of where the present invention has utility includes spread-spectrum technologies in the transmission and the detection of data signals.
The present invention relates to multi-valued coding of sequences. A sequence is a series of digital symbols which can be represented in a signal consisting of separate elements or symbols (sometimes called chips) with discrete and distinguishable values. For the purpose of simplicity discrete values of signals will be represented here as numbers in origin 0 or as amplitude of a signal. It should be clear that other physical properties, for example a pulse position or the phase of a carrier signal or the polarization of a carrier signal can be used to represent the discrete elements in a sequence. It should also be clear that representation of the symbols as numbers is for convenience only.
In current applications of spread spectrum technologies used for the transmission of signals, such as in wireless communications, a digital data symbol is translated into a sequence consisting of a certain number of binary symbols. The transmission of the sequence will usually be achieved in the same time as the duration of the original data symbol. Instead of sending or receiving one specific discrete signal that represents a data symbol one will send or receive a sequence of (in this case) binary symbols. The generated sequence consists of multiple symbols (also called chips), as opposed to the single data element, and it is said that the signal is ‘spread’.
To enable correct reception of the spreaded data elements each of the original data elements has to be coded by a different sequence, so that at the receiving end it can be determined which data symbol was sent. If different users of a transmission system occupy the same physical channel (such as in radio communications), then distinguishing between the symbols from each individual user requires the assignment of different sequences for the each symbol sent by each user. In present systems, the data symbols are generally binary (0 or 1) and the representing sequences also consist of binary symbols.
A common system for detecting the presence of a certain sequence in a received signal is by way of correlation. This method involves the generation of the to be detected sequence at the receiving end, and comparing this locally generated sequence with the received signal.
The principle of correlation between two sequences for detection and synchronization works in such as way that the assigned values of consecutive elements in two sequences will be multiplied and the result added to a sum. When two sequences are synchronized and identical the sum reaches a maximum value. When the two sequences are different or are not synchronized the sum ideally should be lower than when the sequences are identical and synchronized.
This discrete form of correlation is generally expressed in formula as:
      C    ⁡          (      j      )        =            1      N        ⁢                  ∑                  i          =          1                N            ⁢                          ⁢                        a          i                ⁢                              a                          i              +              j                                .                    This expression determines the (normalized) autocorrelation of the sequence A with N elements ai. For the (normalized) cross-correlation of two different sequences A and B with N elements ai and bi the following expression determines the cross-correlation:
      C    ⁡          (      j      )        =            1      N        ⁢                  ∑                  i          =          1                N            ⁢                          ⁢                        a          i                ⁢                  b                      i            +            j                              
The correlation method can be used to synchronize the locally generated sequence with a known received sequence by “searching” for an alignment wherein the correlation value between the two sequences has or exceeds a certain value.
The correlation method can also be used for detection of a certain sequence when it is part of a received sequence. In that case synchronization of the locally generated sequence with the received sequence should be assured. Also the correlation value of the received and the locally generated sequence should be equal to or exceed a certain value when the two sequences are identical.
Such a system for receiving and detecting sequences is less sensitive to noise and errors when the correlation value is high when sequences are synchronized and identical and very low when sequences are different or not synchronized. The known way to achieve a certain correlation performance is to use a selected group of binary sequences, wherein the autocorrelation shows a single high peak and the crosscorrelation is low. It is known from the literature that binary m-sequences or pseudo-random sequences have such a performance.
The present approach limits the number of usable sequences in applications such as communication systems. There is a need for a method to detect sequences that do not comply with certain statistical requirements. Such a novel method is one aspect of the present invention.
The properties of pseudo-random and other digital sequences are documented and widely used in present communication systems. It may be necessary (for instance for security reasons or in heavily congested situations) to make sequences look more alike and less distinguishable for present methods, while still being able to distinguish between the sequences. This is another aspect of the present invention.
A novel way is to increase the correlation value when elements are identical and subtract a higher value when elements are not equal. This method was described by the inventor in U.S. Non-Provisional patent application Ser. No. 11/042,645, filed Jan. 25, 2005, entitled MULTI-VALUED SCRAMBLING AND DESCRAMBLING OF DIGITAL DATA ON OPTICAL DISKS AND OTHER STORAGE MEDIA and in U.S. Non-Provisional patent application Ser. No. 11/065,836 filed Feb. 25, 2005, entitled GENERATION AND DETECTION OF NON-BINARY DIGITAL SEQUENCES; both are incorporated herein by reference.
A novel way to determine and improve the correlation performance for detection of sequences is one aspect of the present invention.
It is clear to the inventor that detection of a sequence is determining if a received sequence has a certain number of elements in a certain order. Correlation methods in essence execute only one part of that process: it determines if a received sequence has the same number of certain elements as the to be detected sequence.
Binary maximum length or m-sequences have an equal or almost equal number of ‘0’ and ‘1’ symbols. Their distribution over the sequence is such that there is only one position in the autocorrelation graph where all symbols are aligned. In all other shifted (or not-synchronized) positions there is almost an equal number or matching and non-matching symbols.
It should be clear that for binary sequences wherein either the ‘0’ symbols or the ‘1’ symbols dominate in a significant way the difference between the highest and lowest correlation values will be smaller than when the there are close to equal numbers of ‘0’ and ‘1’ symbols.
Binary sequences that ‘look alike’ or that have a relatively great number of identical symbols at corresponding positions are difficult to distinguish from each other. The present invention addresses these shortcomings and limitations in present and prior art.
Sequences presently used in spread-spectrum applications are predominantly of a binary nature. Also a sequence of binary symbols pre-dominantly represents a binary symbol. It is known that a sequence of m binary symbols can represent an n-valued symbol, for n≦2m. This method of assigning more than 2 symbols to a sequence for one user is also known as Multi-coding.
It is another aspect of the present invention to provide a method to create and detect multi-code sequences.